﻿//////////////////////////////////////////////#include <iostream>
//////////////////////////////////////////////#include <string>
//////////////////////////////////////////////#include <cctype>
//////////////////////////////////////////////using namespace std;
//////////////////////////////////////////////int main() 
//////////////////////////////////////////////{int vowel_count = 0;string resultstring1;
//////////////////////////////////////////////	string inputstring;getline(std::cin, inputstring);
//////////////////////////////////////////////	
//////////////////////////////////////////////	
//////////////////////////////////////////////	
//////////////////////////////////////////////
//////////////////////////////////////////////	for (char ch : inputstring) {
//////////////////////////////////////////////		if (tolower(ch) == 'a' || tolower(ch) == 'e' || tolower(ch) == 'i' ||
//////////////////////////////////////////////			tolower(ch) == 'o' || tolower(ch) == 'u') 
//////////////////////////////////////////////		{
//////////////////////////////////////////////			++vowel_count;
//////////////////////////////////////////////		}
//////////////////////////////////////////////		else {
//////////////////////////////////////////////			resultstring1 += ch;
//////////////////////////////////////////////		}
//////////////////////////////////////////////	}
//////////////////////////////////////////////
//////////////////////////////////////////////	cout << vowel_count << endl;
//////////////////////////////////////////////	cout << resultstring1 << endl;
//////////////////////////////////////////////	return 0;
//////////////////////////////////////////////}
////////////////////////////////////////////
////////////////////////////////////////////
////////////////////////////////////////////
////////////////////////////////////////////
////////////////////////////////////////#include<vector>
////////////////////////////////////////#include<iostream>
////////////////////////////////////////using namespace std;
////////////////////////////////////////struct node
////////////////////////////////////////{
////////////////////////////////////////	int date;
////////////////////////////////////////	struct node* left=nullptr;
////////////////////////////////////////	struct node* right=nullptr;
////////////////////////////////////////	node(int t)
////////////////////////////////////////	{
////////////////////////////////////////		date = t;
////////////////////////////////////////	}
////////////////////////////////////////};
////////////////////////////////////////struct node* build(vector<int>pre, vector<int>in, int& prei, int inbegin, int inend)
////////////////////////////////////////{
//////////////////////////////////////// 	int rooti = inbegin;
////////////////////////////////////////	if (inbegin > inend)
////////////////////////////////////////	{
////////////////////////////////////////		return nullptr;
////////////////////////////////////////	}
////////////////////////////////////////	else
////////////////////////////////////////	{
////////////////////////////////////////		while (pre[prei] != in[rooti]&&rooti<=inend)
////////////////////////////////////////		{
////////////////////////////////////////			rooti++;
////////////////////////////////////////		}
////////////////////////////////////////	}
////////////////////////////////////////	
////////////////////////////////////////	struct node* newnode = new struct node(pre[prei]);
////////////////////////////////////////	prei++;
////////////////////////////////////////	newnode->left = build(pre, in, prei, inbegin, rooti - 1);
////////////////////////////////////////	newnode->right = build(pre, in, prei, rooti + 1, inend);
////////////////////////////////////////	return newnode;
////////////////////////////////////////}
////////////////////////////////////////struct node* ldr(struct node*node1)
////////////////////////////////////////{
////////////////////////////////////////	if (node1 == nullptr)
////////////////////////////////////////	{
////////////////////////////////////////		return null;
////////////////////////////////////////	}
////////////////////////////////////////	else
////////////////////////////////////////	{
////////////////////////////////////////		ldr(node1->left);
////////////////////////////////////////		ldr(node1->right);
////////////////////////////////////////		cout << node1->date<<' ';
////////////////////////////////////////	}
////////////////////////////////////////}
////////////////////////////////////////int main()
////////////////////////////////////////{
////////////////////////////////////////	int n;
////////////////////////////////////////	vector<int>pre;
////////////////////////////////////////	vector<int>in;
////////////////////////////////////////	cin >> n;
////////////////////////////////////////	for (int i = 0; i < n; i++)
////////////////////////////////////////	{
////////////////////////////////////////		int t;
////////////////////////////////////////		cin >> t;
////////////////////////////////////////		pre.push_back(t);
////////////////////////////////////////	}
////////////////////////////////////////	for (int i = 0; i < n; i++)
////////////////////////////////////////	{
////////////////////////////////////////		int t;
////////////////////////////////////////		cin >> t;
////////////////////////////////////////		in.push_back(t);
////////////////////////////////////////	}
////////////////////////////////////////	int i = 0;
////////////////////////////////////////	struct node* head = build(pre, in, i, 0, pre.size() - 1);
////////////////////////////////////////	ldr(head);
////////////////////////////////////////	return 0;
////////////////////////////////////////}
////////////////////////////////////////
//////////////////////////////////////////
//////////////////////////////////////////
//////////////////////////////////////////
//////////////////////////////////////////
//////////////////////////////////////#include<iostream>
//////////////////////////////////////#include<vector>
//////////////////////////////////////using namespace std;
//////////////////////////////////////int main()
//////////////////////////////////////{
//////////////////////////////////////	int n;
//////////////////////////////////////	cin >> n;
//////////////////////////////////////	if (n < 3)
//////////////////////////////////////	{
//////////////////////////////////////		cout << "false";
//////////////////////////////////////		return 0;
//////////////////////////////////////	}
//////////////////////////////////////	vector<int>nums;
//////////////////////////////////////	int rooti = 0;
//////////////////////////////////////	for (int i = 0; i < n; i++)
//////////////////////////////////////	{
//////////////////////////////////////		int t;
//////////////////////////////////////		cin >> t;
//////////////////////////////////////		nums.push_back(t);
//////////////////////////////////////	}
//////////////////////////////////////	for (int i = 1; i < n; i++)
//////////////////////////////////////	{
//////////////////////////////////////		if (nums[i - 1] < nums[i])
//////////////////////////////////////		{
//////////////////////////////////////			rooti = i;
//////////////////////////////////////		}
//////////////////////////////////////		else
//////////////////////////////////////		{
//////////////////////////////////////			break;
//////////////////////////////////////		}
//////////////////////////////////////	}
//////////////////////////////////////	for (int i = rooti; i < n - 1; i++)
//////////////////////////////////////	{
//////////////////////////////////////		if (nums[i + 1] >= nums[i])
//////////////////////////////////////		{
//////////////////////////////////////			cout << "false";
//////////////////////////////////////			return 0;
//////////////////////////////////////		}
//////////////////////////////////////	}
//////////////////////////////////////	cout << "true";
//////////////////////////////////////	return 0;
//////////////////////////////////////}
////////////////////////////////////
////////////////////////////////////
////////////////////////////////////
////////////////////////////////////#include<iostream>
////////////////////////////////////#include<vector>
////////////////////////////////////using namespace std;
////////////////////////////////////int num[10][10];
////////////////////////////////////int main()
////////////////////////////////////{
////////////////////////////////////	int printans = 0;
////////////////////////////////////	for (int i = 0; i < 3; i++)
////////////////////////////////////	{
////////////////////////////////////		for (int j = 0; j < 3; j++)
////////////////////////////////////		{
////////////////////////////////////			cin >> num[i][j];
////////////////////////////////////		}
////////////////////////////////////	}
////////////////////////////////////	for (int i = 0; i < 3; i++)
////////////////////////////////////	{
////////////////////////////////////		for (int j = 0; j < 3; j++)
////////////////////////////////////		{
////////////////////////////////////			if (num[i][j] == 0)
////////////////////////////////////			{
////////////////////////////////////				int ans = 0x3f3f;
////////////////////////////////////				int ip2=4;
////////////////////////////////////				int jp2=4;
////////////////////////////////////				for (int ip = 0; ip < 3; ip++)
////////////////////////////////////				{
////////////////////////////////////					for (int jp = 0; jp < 3; jp++)
////////////////////////////////////					{
////////////////////////////////////						if (num[ip][jp] > 1)
////////////////////////////////////						{
////////////////////////////////////							int t = (max(ip, i) - min(ip, i)) + (max(jp, j) - min(jp, j));
////////////////////////////////////							if (ans > t)
////////////////////////////////////							{
////////////////////////////////////								ip2 = ip;
////////////////////////////////////								jp2 = jp;
////////////////////////////////////								ans = t;
////////////////////////////////////							}
////////////////////////////////////						}
////////////////////////////////////					}
////////////////////////////////////				}
////////////////////////////////////				if (ip2 != 4 && jp2 != 4)
////////////////////////////////////				{
////////////////////////////////////					num[ip2][jp2]--;
////////////////////////////////////					num[i][j]++;
////////////////////////////////////					printans += ans;
////////////////////////////////////				}
////////////////////////////////////			}
////////////////////////////////////		}
////////////////////////////////////	}
////////////////////////////////////	cout << printans;
////////////////////////////////////	return 0;
////////////////////////////////////}
//////////////////////////////////
//////////////////////////////////
//////////////////////////////////
//////////////////////////////////
////////////////////////////////////#include<iostream>
////////////////////////////////////using namespace std;
////////////////////////////////////int dx[4] = { 0,0,1,-1 };
////////////////////////////////////int dy[4] = { 1,-1,0,0 };
////////////////////////////////////int num[1010][1010];
////////////////////////////////////int area, ret, m, n;
////////////////////////////////////bool vis[1010][1010];
////////////////////////////////////void dfs(int row,int col)
////////////////////////////////////{
////////////////////////////////////	area++;
////////////////////////////////////	for (int k = 0; k < 4; k++)
////////////////////////////////////	{
////////////////////////////////////		int x = row + dx[k], y = col + dy[k];
////////////////////////////////////		if (x >= 0 && x < m && y >= 0 && y < n && num[x][y] && !vis[x][y])
////////////////////////////////////		{
////////////////////////////////////			vis[x][y] = true;
////////////////////////////////////			dfs( x, y);
////////////////////////////////////		}
////////////////////////////////////	}
////////////////////////////////////}
////////////////////////////////////int main()
////////////////////////////////////{
////////////////////////////////////	cin >> m >> n;
////////////////////////////////////	for (int i = 0; i < m; i++)
////////////////////////////////////	{
////////////////////////////////////		for (int j = 0; j < n; j++)
////////////////////////////////////		{
////////////////////////////////////			cin >> num[i][j];
////////////////////////////////////		}
////////////////////////////////////	}
////////////////////////////////////	for (int i = 0; i < m; i++)
////////////////////////////////////	{
////////////////////////////////////		for (int j = 0; j < n; j++)
////////////////////////////////////		{
////////////////////////////////////			if (!vis[i][j] && num[i][j] == 1)
////////////////////////////////////			{
////////////////////////////////////				area = 0;
////////////////////////////////////				vis[i][j] = true;
////////////////////////////////////				dfs(i, j);
////////////////////////////////////				ret = max(ret, area);
////////////////////////////////////			}
////////////////////////////////////		}
////////////////////////////////////	}
////////////////////////////////////	cout << ret;
////////////////////////////////////
////////////////////////////////////	return 0;
////////////////////////////////////}
////////////////////////////////////
////////////////////////////////////
////////////////////////////////
////////////////////////////////
//////////////////////////////////#include<iostream>
//////////////////////////////////using namespace std;
//////////////////////////////////int main()
//////////////////////////////////{
//////////////////////////////////    int ax1, ay1, ax2, ay2, bx1, by1, bx2, by2;
//////////////////////////////////    cin >> ax1 >> ay1 >> ax2 >> ay2 >> bx1 >> by1 >> bx2 >> by2;
//////////////////////////////////    int area = (ax2 - ax1) * (ay2 - ay1) + (bx2 - bx1) * (by2 - by1);
//////////////////////////////////    int width = min(ax2, bx2) - max(ax1, bx1);
//////////////////////////////////    int heigh = min(ay2, by2) - max(ay1, by1);
//////////////////////////////////    cout<<area - (max(heigh, 0) * max(width, 0));
//////////////////////////////////	return 0;
//////////////////////////////////}
////////////////////////////////
////////////////////////////////
////////////////////////////////
////////////////////////////////
////////////////////////////////
////////////////////////////////
////////////////////////////////#include<iostream>
////////////////////////////////#include<string>
////////////////////////////////using namespace std;
////////////////////////////////int main()
////////////////////////////////{
////////////////////////////////    int num = 1;
////////////////////////////////    int first = 1;
////////////////////////////////    string str;
////////////////////////////////    int n;
////////////////////////////////    cin >> n;
////////////////////////////////    cin >> str;
////////////////////////////////    if (n < 4)
////////////////////////////////    {
////////////////////////////////        for (int i = 0; i < str.size(); i++)
////////////////////////////////        {
////////////////////////////////            if (str[i] == 'u')
////////////////////////////////            {
////////////////////////////////                if (num == 1)
////////////////////////////////                {
////////////////////////////////                    num = n;
////////////////////////////////
////////////////////////////////                }
////////////////////////////////                else
////////////////////////////////                {
////////////////////////////////                    num--;
////////////////////////////////                }
////////////////////////////////            }
////////////////////////////////            else
////////////////////////////////            {
////////////////////////////////                if (num == n)
////////////////////////////////                {
////////////////////////////////                    num = 1;
////////////////////////////////                }
////////////////////////////////                else
////////////////////////////////                {
////////////////////////////////                    num++;
////////////////////////////////                }
////////////////////////////////            }
////////////////////////////////        }
////////////////////////////////        for (int i = 1; i <= n; i++)
////////////////////////////////            cout << i << " ";
////////////////////////////////        cout << endl << num;
////////////////////////////////    }
////////////////////////////////    else
////////////////////////////////    {
////////////////////////////////        for (int i = 0; i < str.size(); i++)
////////////////////////////////        {
////////////////////////////////            if (num == 1 && first == 1 && str[i] == 'u')
////////////////////////////////            {
////////////////////////////////                num = n;
////////////////////////////////                first = n - 3;
////////////////////////////////            }
////////////////////////////////            else if (num == n && first == n - 3 && str[i] == 'd')
////////////////////////////////            {
////////////////////////////////                num = first = 1;
////////////////////////////////            }
////////////////////////////////            else if (first != n - 3 && num == first + 3 && str[i] == 'd')
////////////////////////////////            {
////////////////////////////////                first = first + 3;
////////////////////////////////                num++;
////////////////////////////////            }
////////////////////////////////            else if (first != 1 && num == first && str[i] == 'u')
////////////////////////////////            {
////////////////////////////////                first = first - 3;
////////////////////////////////                num--;
////////////////////////////////            }
////////////////////////////////            else if (str[i] == 'd')
////////////////////////////////            {
////////////////////////////////                num++;
////////////////////////////////            }
////////////////////////////////            else
////////////////////////////////            {
////////////////////////////////                num--;
////////////////////////////////            }
////////////////////////////////        }
////////////////////////////////        for (int i = first; i <= first + 3; i++)
////////////////////////////////        {
////////////////////////////////            cout << i << " ";
////////////////////////////////        }
////////////////////////////////        cout << endl << num;
////////////////////////////////    }
////////////////////////////////    return 0;
////////////////////////////////}
//////////////////////////////
//////////////////////////////
//////////////////////////////
//////////////////////////////
//////////////////////////////#include<iostream>
//////////////////////////////#include<vector>
//////////////////////////////#include<string>
//////////////////////////////using namespace std;
//////////////////////////////int main()
//////////////////////////////{
//////////////////////////////	vector<string>c;
//////////////////////////////	string a;
//////////////////////////////	cin >> a;
//////////////////////////////	string b;
//////////////////////////////	for (auto& q : a)
//////////////////////////////	{
//////////////////////////////		char p=toupper(q);
//////////////////////////////		b.push_back(p);
//////////////////////////////	}
//////////////////////////////	c.push_back(b);
//////////////////////////////	for (auto q : c)
//////////////////////////////	{
//////////////////////////////		cout << q;
//////////////////////////////	}
//////////////////////////////	return 0;
//////////////////////////////}
////////////////////////////
////////////////////////////
////////////////////////////
////////////////////////////
////////////////////////////#include<iostream>
////////////////////////////#include<algorithm>
////////////////////////////#include<vector>
////////////////////////////using namespace std;
////////////////////////////class solution {
////////////////////////////public:
////////////////////////////    int morethanhalfnum_solution(vector<int>& numbers)
////////////////////////////    {
////////////////////////////        int cur = 1;
////////////////////////////        int dest = 0;
////////////////////////////        vector<int> v;
////////////////////////////        int len = numbers.size();
////////////////////////////        int s = len / 2;
////////////////////////////        sort(numbers.begin(), numbers.end());
////////////////////////////        while (cur != numbers.size())
////////////////////////////        {
////////////////////////////            if (numbers[dest] == numbers[cur])
////////////////////////////            {
////////////////////////////                cur++;
////////////////////////////
////////////////////////////            }
////////////////////////////            else
////////////////////////////            {
////////////////////////////                v.push_back(cur - dest);
////////////////////////////                dest = cur;
////////////////////////////                cur++;
////////////////////////////
////////////////////////////            }
////////////////////////////
////////////////////////////        }
////////////////////////////        for (auto e : v)
////////////////////////////        {
////////////////////////////            if (e > s)
////////////////////////////            {
////////////////////////////                return e;
////////////////////////////            }
////////////////////////////        }
////////////////////////////        return 1;
////////////////////////////    }
////////////////////////////};
//////////////////////////
//////////////////////////
//////////////////////////
//////////////////////////
//////////////////////////#include<iostream>
//////////////////////////#include<algorithm>
//////////////////////////#include<vector>
//////////////////////////using namespace std;
//////////////////////////class solution {
//////////////////////////public:
//////////////////////////	int morethanhalfnum_solution(vector<int>& numbers)
//////////////////////////	{
//////////////////////////		int cur = 1;
//////////////////////////		int dest = 0;
//////////////////////////		vector<int> v;
//////////////////////////		int len = numbers.size();
//////////////////////////		int s = len / 2;
//////////////////////////		sort(numbers.begin(), numbers.end());
//////////////////////////		while (cur <= numbers.size())
//////////////////////////		{
//////////////////////////			if (numbers[dest] == numbers[cur])
//////////////////////////			{
//////////////////////////				cur++;
//////////////////////////			}
//////////////////////////			if (cur == 7 || numbers[dest] != numbers[cur])
//////////////////////////			{
//////////////////////////				v.push_back(cur - dest);
//////////////////////////				dest = cur;
//////////////////////////				cur++;
//////////////////////////			}
//////////////////////////		}
//////////////////////////		for (auto e : v)
//////////////////////////		{
//////////////////////////			if (e > s)
//////////////////////////			{
//////////////////////////				return e;
//////////////////////////			}
//////////////////////////		}
//////////////////////////		return 0;
//////////////////////////	}
//////////////////////////};
////////////////////////
////////////////////////
////////////////////////
////////////////////////
////////////////////////// // int num[90000];//全局定义一个数组这是这个数组里面都是0
////////////////////////// // class solution {
////////////////////////// // public:
////////////////////////// //     int morethanhalfnum_solution(vector<int>& numbers)
////////////////////////// //     {
////////////////////////// //        for(int i=0;i<numbers.size();i++)
////////////////////////// //        {
////////////////////////// //         num[numbers[i]]++;//统计每个数字的个数
////////////////////////// //        }
////////////////////////// //        for(int i=0;i<numbers.size();i++)
////////////////////////// //        {
////////////////////////// //         if(num[numbers[i]]>(numbers.size()/2))
////////////////////////// //         {
////////////////////////// //             return numbers[i];//逐个判断这里面每个数字的个数是否大于长度的二分之1
////////////////////////// //         }
////////////////////////// //        }
////////////////////////// //        return 0;
////////////////////////// //     }
////////////////////////// // };
////////////////////////
//////////////////////////那么接下来用c++来转化一下上面的代码
////////////////////////#include <vector>
////////////////////////#include<iostream>
////////////////////////using namespace std;
//////////////////////////class solution {
//////////////////////////public:
//////////////////////////	int morethanhalfnum_solution(vector<int>&& numbers) {
//////////////////////////		vector<int>v(90000, 0);//这里的意思仍然是先创建一个数组数组的大小是90000其中元素都是0
//////////////////////////		for (auto c : numbers)
//////////////////////////		{
//////////////////////////			v[c]++;//统计每个数字出现的次数;
//////////////////////////		}
//////////////////////////		for (auto c : numbers)
//////////////////////////		{
//////////////////////////			if (v[c] > (numbers.size() / 2))//遍历找到出现次数大于长度一半的数字
//////////////////////////			{
//////////////////////////				return c;
//////////////////////////			}
//////////////////////////		}
//////////////////////////		return 0;
//////////////////////////	}
//////////////////////////};
////////////////////////#include<iostream>
////////////////////////#include<algorithm>
////////////////////////#include<vector>
////////////////////////using namespace std;
////////////////////////class Solution {
////////////////////////public:
////////////////////////	int MoreThanHalfNum_Solution(vector<int>&& numbers)
////////////////////////	{
////////////////////////		int cur = 1;
////////////////////////		int dest = 0;
////////////////////////		vector<int> v(10000, 0);//第一处修改
////////////////////////		int len = numbers.size();
////////////////////////		int s = len / 2;
////////////////////////		sort(numbers.begin(), numbers.end());
////////////////////////		while (cur <= numbers.size())
////////////////////////		{
////////////////////////			if (numbers[dest] == numbers[cur])
////////////////////////			{
////////////////////////				cur++;
////////////////////////			}
////////////////////////			if (cur == 9 || numbers[dest] != numbers[cur])//第二处修改
////////////////////////			{
////////////////////////				v[numbers[dest]] = cur - dest;
////////////////////////				dest = cur;
////////////////////////				cur++;
////////////////////////			}
////////////////////////		}
////////////////////////		int max = 0;
////////////////////////		for (int i = 0; i < numbers.size(); i++)//第三处修改
////////////////////////		{
////////////////////////			if (max <= v[numbers[i]])
////////////////////////			{
////////////////////////				max = numbers[i];
////////////////////////			}
////////////////////////		}
////////////////////////		return max;
////////////////////////	}
////////////////////////};
////////////////////////
////////////////////////int main()
////////////////////////{
////////////////////////	Solution a;
////////////////////////	cout<<a.MoreThanHalfNum_Solution({ 2,2,2,2,3,3,3,3,3 });
////////////////////////
////////////////////////	return 0;
////////////////////////}
//////////////////////
//////////////////////
//////////////////////#include<queue>
//////////////////////#include<iostream>
//////////////////////#include<algorithm>
//////////////////////using namespace std;
//////////////////////int num[300];
//////////////////////class Solution {
//////////////////////public:
//////////////////////    int lengthOfLongestSubstring(string s) {
//////////////////////        queue<char>q;
//////////////////////        int max_ans = 0;
//////////////////////        for (auto c : s)
//////////////////////        {
//////////////////////            //cout << q.size();
//////////////////////
//////////////////////            if (q.empty())
//////////////////////            {
//////////////////////                q.push(c);
//////////////////////                num[c]++;
//////////////////////            }
//////////////////////            else if (num[c] == 0)
//////////////////////            {
//////////////////////                q.push(c);
//////////////////////                num[c]++;
//////////////////////            }
//////////////////////            else if (num[c] >= 1)
//////////////////////            {
//////////////////////                int size = q.size();
//////////////////////                max_ans = max(max_ans, size);
//////////////////////                while (!q.empty())
//////////////////////                {
//////////////////////                    if (q.front() == c)
//////////////////////                    {
//////////////////////                        q.pop();
//////////////////////                        q.push(c);
//////////////////////                        num[c] = 1;
//////////////////////                        break;
//////////////////////                    }
//////////////////////                    else
//////////////////////                    {
//////////////////////                        num[q.front()]--;
//////////////////////                        q.pop();
//////////////////////                        
//////////////////////                    }
//////////////////////                }
//////////////////////            }
//////////////////////        }
//////////////////////        int size = q.size();
//////////////////////        max_ans = max(max_ans, size);
//////////////////////        return max_ans;
//////////////////////    }
//////////////////////};
//////////////////////int uniquePaths(int m, int n)
//////////////////////{
//////////////////////    vector<vector<int>>nums(1010, vector<int>(1010,0));
//////////////////////        nums[1][2] = 1;
//////////////////////    for (int i = 1; i <= m; i++)
//////////////////////    {
//////////////////////        for (int j = 1; j <= n; j++)
//////////////////////        {
//////////////////////            nums[i][j] = nums[i - 1][j] + nums[i][j - 1];
//////////////////////        }
//////////////////////    }
//////////////////////    return nums[m][n];
//////////////////////}
//////////////////////int main()
//////////////////////{
//////////////////////    cout<<uniquePaths(3, 4);
//////////////////////
//////////////////////
//////////////////////	return 0;
//////////////////////}
////////////////////
////////////////////
////////////////////
////////////////////#include<iostream>
////////////////////#include<vector>
////////////////////using namespace std;
////////////////////int ans = 0;
////////////////////int dx[4] = { 0,0,-1,1 };
////////////////////int dy[4] = { 1,-1,0,0 };
////////////////////vector<vector<int>>q(1010, vector<int>(1010, 0));
////////////////////void dfs(vector<vector<char>>& grid, int x, int y)
////////////////////{
////////////////////    q[x][y] = true;
////////////////////    ans++;
////////////////////    for (int i = 0; i < 4; i++)
////////////////////    {
////////////////////        int kx = x + dx[i];
////////////////////        int ky = y + dy[i];
////////////////////        if (kx >= 0 && ky >= 0 && kx < grid.size() && ky <= grid[x].size() && !q[kx][ky] && grid[kx][ky])
////////////////////        {
////////////////////            dfs(grid, kx, ky);
////////////////////        }
////////////////////    }
////////////////////    return;
////////////////////}
////////////////////int numIslands(vector<vector<char>>& grid) {
////////////////////    for (int i = 0; i < grid.size(); i++)
////////////////////    {
////////////////////        for (int j = 0; j < grid[i].size(); j++)
////////////////////        {
////////////////////            if (grid[i][j] == 1)
////////////////////            {
////////////////////                dfs(grid, i, j);
////////////////////            }
////////////////////        }
////////////////////    }
////////////////////    return ans;
////////////////////}
////////////////////int main()
////////////////////{
////////////////////	int N, V;
////////////////////	cin >> N >> V;
////////////////////	for (int i = 1; i <= N; i++)
////////////////////	{
////////////////////		cin >> v1[i] >> n1[i];
////////////////////	}
////////////////////	for (int i = 1; i <= N; i++)
////////////////////	{
////////////////////		for (int j = V; j >= v1[i]; j--)
////////////////////		{
////////////////////			v[j] = max(v[j], v[j - v1[i]] + n1[i]);
////////////////////		}
////////////////////	}
////////////////////	cout << v[V];
////////////////////
////////////////////	return 0;
////////////////////}
//////////////////
//////////////////
//////////////////#include<vector>
//////////////////#include<string>
//////////////////#include<iostream>
//////////////////using namespace std;
//////////////////bool strmach(const char* spath, const char* path)
//////////////////{
//////////////////    if (*path == '\0' && *spath == '\0')
//////////////////    {
//////////////////        return true;
//////////////////    }
//////////////////    else if (*path == '\0' || *spath == '\0')
//////////////////    {
//////////////////        return false;
//////////////////    }
//////////////////    else if (*path == '.')
//////////////////    {
//////////////////        return strmach(spath + 1, path + 1);
//////////////////    }
//////////////////    else if (*path == *spath)
//////////////////    {
//////////////////        return strmach(spath + 1, path + 1);
//////////////////    }
//////////////////    else if (*path == '*')
//////////////////    {
//////////////////        return strmach(spath + 1, path + 1) || strmach(spath, path + 1) || strmach(spath + 1, path);
//////////////////    }
//////////////////    return false;
//////////////////}
//////////////////bool isMatch(string s, string p)
//////////////////{
//////////////////    return strmach(s.c_str(), p.c_str());
//////////////////}
//////////////////int main()
//////////////////{
//////////////////    string s = "aa";
//////////////////    string p = "a*";
//////////////////   cout<< isMatch(s, p);
//////////////////
//////////////////
//////////////////	return 0;
//////////////////}
//////////////////
//////////////////
//////////////////
//////////////////
//////////////////
//////////////////
////////////////
////////////////
////////////////
////////////////
////////////////#include<iostream>
////////////////using namespace std;
////////////////int main()
////////////////{
////////////////	int m, n, a, b;
////////////////	m = 2, n = 2, a = 2, b = 2;
////////////////	(m = a >= b)&&
////////////////		(n = a > b);
////////////////	cout <<"m=" << m <<" " << "n=" << n;
////////////////
////////////////
////////////////
////////////////	return 0;
////////////////}
//////////////
//////////////
//////////////
//////////////
//////////////#include<iostream>
//////////////using namespace std;
//////////////int main()
//////////////{
//////////////	int n, m, a, b;
//////////////	n = 2, m = 2, a = 2, b = 2;
//////////////	m = a > b && (cout << (n = a > b))<<endl;
//////////////	cout << m << n;
//////////////	return 0;
//////////////}
////////////
////////////
////////////
////////////
//////////////#include<iostream>
//////////////using namespace std;
//////////////int main()
//////////////{
//////////////	char str[3][4] = { "123","456","789" };
//////////////	str[0][3] = '*';
//////////////	str[1][3] = '+';
//////////////	str[2][1] = 0;
//////////////	printf("%s", str[0]);
//////////////
//////////////
//////////////	return 0;
//////////////}
////////////
////////////
////////////
////////////
////////////
////////////#include<iostream>
////////////#include<vector>
////////////#include<string>
////////////using namespace std;
////////////    vector<int> findAnagrams(string s, string p) {
////////////        vector<int>hash1(400, 0);
////////////        vector<int>hash2(400, 0);
////////////        for (auto c : p)
////////////        {
////////////            hash1[c]++;
////////////        }
////////////        int left = 0;
////////////        vector<int>q;
////////////        for (int right = 0; right < s.size(); right++)
////////////        {
////////////            bool flag = true;
////////////            hash2[s[right]]++;
////////////            if (right - left + 1 == p.size())
////////////            {
////////////                for (int i = 0; i < 400; i++)
////////////                {
////////////                    if (hash2[i] > 0)
////////////                    {
////////////                        printf("%c", i);
////////////                    }
////////////                }
////////////                cout << endl;
////////////                for (auto c : p)
////////////                {
////////////                    if (hash2[c] != hash1[c])
////////////                    {
////////////                        left++;
////////////                        flag = false;
////////////                        break;
////////////                    }
////////////                }
////////////                if (flag == true)
////////////                {
////////////                    q.push_back(left);
////////////                }
////////////            }
////////////        }
////////////        return q;
////////////    }
////////////
////////////int main()
////////////{
////////////    string a = "cbaebabacd";
////////////    string b = "abc";
////////////     findAnagrams(a,b);
////////////
////////////
////////////
////////////	return 0;
////////////}
//////////
//////////
//////////
//////////
//////////#include<string>
//////////#include<iostream>
//////////#include<unordered_map>
//////////using namespace std;
//////////int num[100010];
//////////int hash[10010];
//////////int main()
//////////{
//////////	string a = "abcdaaabbcefg";
//////////	for (int i = 0; i < a.size(); i++)
//////////	{
//////////		num[a[i]]++;
//////////	}
//////////	return 0;
//////////}
////////
////////
////////
////////
////////#include<iostream>
////////#include<algorithm>
////////using namespace std;
////////int main()
////////{
////////	int n;
////////	cin >> n;
////////	for (int i = 0, j = n - 1; i < n&&j >= 0; i++, j--)
////////	{
////////		for (int p = 0; p <= max(i, j); p++)
////////		{
////////			if (p == i || p == j)
////////			{
////////				cout << "*";
////////			}
////////			else
////////			{
////////				cout << " ";
////////			}
////////		}
////////		cout << endl;
////////	}
////////
////////	return 0;
////////}
//////
//////
//////
//////
//////#include<iostream>
//////using namespace std;
//////int main()
//////{
//////	int x = 0;
//////	int h[10010];
//////	memset(h, -1, sizeof(h));
//////	for (auto c : h)
//////	{
//////		cout << c << ' ';
//////	}
//////
//////
//////	return 0;
//////}
////
////
////
////
////
////#include <iostream>
////#include<vector>
////using namespace std;
////
////int main() {
////    int n, q;
////    cin >> n >> q;
////    vector<int>num;
////    for (int i = 0; i < n; i++)
////    {
////        int a;
////        cin >> a;
////        num.push_back(a);
////    }
////    vector<int>nums;
////    nums[0] = num[0];
////    for (int i = 1; i < num.size(); i++)
////    {
////        nums[i] = nums[i - 1] + num[i];
////    }
////    while (q--)
////    {
////        int a, b;
////        cin >> a >> b;
////        int t = nums[b - 1] - nums[a - 1] + num[a - 1];
////        cout << t << endl;
////    }
////}
//
//
//
//
//
//#include <iostream>
//using namespace std;
//int num[1010][1010];
//int dp[1010][1010];
//int main() {
//    int n, m, q;
//    cin >> n >> m >> q;
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            cin >> num[i][j];
//        }
//    }
//    for (int i = 1; i <= n; i++)
//    {
//        for (int j = 1; j <= m; j++)
//        {
//            dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + num[i][j];
//            cout << dp[i][j] << ' ';
//        }
//        cout << endl;
//    }
//
//    return 0;
//}





#include <iostream>
#include<vector>
using namespace std;

int main() {
    int n, q;
    cin >> n;
    cin >> q;
    vector<int>arr;
    int k = 0;
    while (cin >> k)
    {
        arr.push_back(k);
    }l

    int l, r;
    vector<int>ret;
    int num = 0;
    for (int i = 0; i < q; i++)
    {
        cin >> l;
        cin >> r;
        for (int j = l; j < r; j++)
        {
            num += arr[j];
        }
        ret.push_back(num);
    }
    for (auto x : ret)
    {
        cout << x << endl;
    }
}